'''
@Author: shj
@Date: 2020-06-01 08:35:34
@LastEditTime: 2020-06-02 10:50:23
@LastEditors: shj
@Description:  调整数组顺序使奇数位于偶数前面
@FilePath: /python3/algorithms/offer_code/13_adjust_array_order_odd_before_even.py
'''
'''
题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
'''
'''
思路
法1 辅助数组
创建辅助数组odd, even，奇数放入odd，偶数放入even，最后拼接辅助数组

法2 插入排序变形

初始化操作：记录一个变量i表示已经将奇数放好的下一个位置，显然最开始i=0,表示还没有一个奇数放好。
j 表示数组的下标，初始值为0， 表示从下标0开始遍历。
    如果遇到偶数，j++
    如果遇到奇数,假设位置为j，就将此奇数插入到i所指的位置，然后i往后移动一个位置，在插入之前，显然会涉及到数据的移动，也就是将[i,j-1]整体往后移动。
    直到整个数组遍历完毕，结束
'''


class Solution:
    def reOrderArray(self, array):
        # write code here
        # 辅助空间
        odd = []
        even = []
        length = len(array)
        for i in range(length):
            # 奇数放入odd，偶数放入even
            print(i)
            if array[i] % 2 != 0:
                odd.append(array[i])
            else:
                even.append(array[i])
        array = odd + even
        return array


# test
array = [1, 2, 3, 4, 5, 6, 7]
sl = Solution()
print(sl.reOrderArray(array))